package code.classic150on2025;

import java.util.List;

public class MultiDP {
    // 97. 交错字符串
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
        if (len3 != len1 + len2)
            return false;
        // dp[i][j][k] s1到j，s2到k交错能否形成s3到i（j+k=i）
        // dp[i][j][k] = if s1[j] == s3[i] dp[i-1][j-1][i-j] if s2[k] == s3[i] dp[i-1][i-k][k-1]
        // 注意到由于i=j+k，所以k可以取决于i和j，所以压缩为2维的DP dp[i][j] k的状态是隐含的
        boolean[][] dp = new boolean[len3 + 1][len1 + 1];
        dp[0][0] = true;
        for (int i = 1; i <= len3; i++) {
            char c3 = s3.charAt(i - 1);
            for (int j = 0; j <= len1; j++) {
                int k = i - j;
                if (k < 0 || k > len2) continue;
                if (j != 0 && s1.charAt(j - 1) == c3) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - 1];
                }
                if (k != 0 && s2.charAt(k - 1) == c3) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
        return dp[len3][len1];
    }

    // 120. 三角形最小路径和
    public int minimumTotal(List<List<Integer>> triangle) {
        int level = triangle.size();
        for (int i = 1; i < level; i++) {
            List<Integer> preLevelList = triangle.get(i - 1);
            int preLevelNum = preLevelList.size();
            List<Integer> nowLevelList = triangle.get(i);
            int nowLevelNum = nowLevelList.size();
            // 第一个
            nowLevelList.set(0, nowLevelList.get(0) + preLevelList.get(0));
            // 第2到n-1个
            for (int j = 1; j < nowLevelNum - 1; j++) {
                nowLevelList.set(j, nowLevelList.get(j) + Math.min(preLevelList.get(j - 1), preLevelList.get(j)));
            }
            // 第n个
            nowLevelList.set(nowLevelNum - 1, nowLevelList.get(nowLevelNum - 1) + preLevelList.get(preLevelNum - 1));
        }
        List<Integer> lastLevel = triangle.get(level - 1);
        int min = Integer.MAX_VALUE;
        for (int num : lastLevel) {
            min = Math.min(min, num);
        }
        return min;
    }

    // 64. 最小路径和
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[m - 1][n - 1];
    }

    // 63. 不同路径 II
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n]; // dp[i][j]表示到（i，j）的路径数量
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 0)
                dp[i][0] = 1;
            else
                break;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 0)
                dp[0][i] = 1;
            else
                break;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    // 5. 最长回文子串
    public String longestPalindrome(String s) {
        int len = s.length();
        // dp[i][j]表示s的i到j子串是不是回文子串
        boolean[][] dp = new boolean[len][len];
        int maxBegin = 0, maxEnd = 0;
        // 子串长度为 1 是回文子串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
            maxBegin = i;
            maxEnd = i;
        }
        // 子串长度为 2 相等是回文子串
        for (int i = 1; i < len; i++) {
            dp[i - 1][i] = s.charAt(i - 1) == s.charAt(i);
            if (dp[i - 1][i]) {
                maxBegin = i - 1;
                maxEnd = i;
            }
        }
        // 子串长度为 3 ~ len
        for (int subLen = 3; subLen <= len; subLen++) {
            for (int start = 0; start + subLen - 1 < len; start++) {
                int end = start + subLen - 1;
                if (s.charAt(start) == s.charAt(end) && dp[start + 1][end - 1]) {
                    dp[start][end] = true;
                    maxBegin = start;
                    maxEnd = end;
                }
            }
        }
        return s.substring(maxBegin, maxEnd + 1);
    }

    // 72. 编辑距离
    public int minDistance(String word1, String word2) {
        // dp[i][j] 表示 word1 的前i个 和 word2 的前j个 互相转换所需最小步骤距离
        int n1 = word1.length(), n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // 初始化：一边取零个字符，这样变为另一边就全是添加操作
        for (int i = 0; i <= n1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= n2; i++) {
            dp[0][i] = i;
        }
        // dp：有三种操作
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                int delete = 1 + dp[i - 1][j];
                int insert = 1 + dp[i][j - 1];
                int modify = 1 + dp[i - 1][j - 1];
                // 如果word1[i]==word2[j]
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    modify--;
                }
                dp[i][j] = Math.min(delete, Math.min(insert, modify));
            }
        }
        return dp[n1][n2];
    }

    // 123. 买卖股票的最佳时机 III
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[] buy1 = new int[len];
        int[] sell1 = new int[len];
        int[] buy2 = new int[len];
        int[] sell2 = new int[len];
        buy1[0] = -prices[0];
        sell1[0] = 0;
        buy2[0] = -prices[0];
        sell2[0] = 0;
        for (int i = 1; i < len; i++) {
            buy1[i] = Math.max(buy1[i - 1], -prices[i]);
            sell1[i] = Math.max(sell1[i - 1], buy1[i] + prices[i]);
            buy2[i] = Math.max(buy2[i - 1], sell1[i] - prices[i]);
            sell2[i] = Math.max(sell2[i - 1], buy2[i] + prices[i]);
        }
        return sell2[len - 1];
    }

    // 188. 买卖股票的最佳时机 IV
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        int[][] buy = new int[k][len];
        int[][] sell = new int[k][len];
        for (int i = 0; i < k; i++) {
            buy[i][0] = -prices[0];
        }
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < k; j++) {
                if (j == 0)
                    buy[j][i] = Math.max(buy[j][i - 1], -prices[i]);
                else
                    buy[j][i] = Math.max(buy[j][i - 1], sell[j - 1][i] - prices[i]);
                sell[j][i] = Math.max(sell[j][i - 1], buy[j][i] + prices[i]);
            }
        }
        return sell[k - 1][len - 1];
    }

    // 221. 最大正方形
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        // dp[i][j] 表示以 i，j 作为右下角的正方形的最大边长
        int max = 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                max = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == '1'){
                dp[0][i] = 1;
                max = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '0')
                    continue;
                dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }
}
